As it has become possible to perform more simple basic logic functions (i.e., AND, OR, NOT, FLIP FLOP, etc.) within a single integrated circuit chip, manufacturers of integrated circuit chips have developed ways of automatically and quickly defining in custom chips, specific functions for specific applications. "Gate array" manufacturers apply custom metallization layers as a final step in a standard manufacturing process in order to connect transistors located within a semiconductor substrate one to the next to perform a particular logic function requested by a customer. For customers who make frequent design changes, who want only small numbers of identical devices, or who may not have fully tested a new design, so-called "user programmable" integrated circuit chips are available. In a user programmable device such as disclosed in U.S. Pat. No. 4,870,302 assigned to Xilinx, Inc., and incorporated herein by reference, there are many pass transistors which can be programmably turned on or off (conductive or nonconductive) to programmably connect or not connect input/output lines of logic blocks to input/output lines of other logic blocks, to connect input/output lines of logic blocks to pins of the IC package, and to connect pins of the IC package to each other. By turning on the proper combination of pass transistors and connecting the proper set of lines a designer can obtain a desired "complex" logic function having the interconnected basic logic functions as its constituents. The designer can reprogram a different design into the chip by turning on different combinations of pass transistors.
As the number of transistors on a single integrated circuit chip has increased and the complexity of logic functions desired by designers has also increased, it has become common to use computer aided design (CAD) to determine the layout necessary to achieve a desired complex logic function. For gate arrays with metal interconnects, automatic placement and routing methods translate a designer's schematic diagram or set of logic equations to a list of metal lines to be formed above the gate array substrate. The list of lines is in turn translated into a mask for physically locating the lines on the chip. For a programmable logic array, automatic placement and routing methods translate the schematic diagram or set of logic equations to a list of pass transistors to be turned on, thereby connecting certain of the metal lines to each other and to combinatorial logic gates to perform the desired logic function (each gate being a group of transistors preconnected to perform a simple logic function such as AND, OR).
Xilinx, Inc., the assignee of the present invention, manufactures logic block arrays (or logic cell arrays) having a higher level of integration than typical programmable logic arrays. A Xilinx logic block array includes an array of logic blocks, each of which can be configured to perform a desired moderately complex logic function (each logic block combining several AND, OR, MUX and FLIP-FLOP gates, for example). The Xilinx logic block array chip also includes interconnect lines which can be programmed to connect individual logic blocks to achieve one or more complex logic functions to be provided by the entire chip. In current Xilinx products, two kinds of configurable blocks are used in a logic block array chip. The chip contains, near its perimeter, input/output logic blocks which can be programmed to connect input buffers or output buffers to the external pins of the chip and to perform some logic functions such as invert. In the interior of the chip are logic blocks which do not offer the input/output buffer option but offer more logic functions within a single block. Other blocks provide clock buffers, pull-up resistors and other functions.
FIG. 1 is a top view schematic showing a corner portion 10 of one of the logic block array chips for which automatic programming is available. The logic array chip of FIG. 1 includes three kinds of logic blocks. Configurable input/output blocks IO1 through IO15 are shown. Configurable logic blocks CLB11-CLB14, CLB21-CLB24, CLB31-CLB34 and CLB41-CLB44 are shown. Each of the configurable input/output and logic blocks includes within it a plurality of combinatorial logic gates such as AND, OR, XOR, INVERT, TRISTATE, FLIPFLOP and MUX which can be configured to perform a plurality of moderately complex logic functions. The CLB's are more fully described in U.S. Pat. No. 4,706,216, incorporated herein by reference. Also shown in FIG. 1 is clock signal buffer block CLK which is connected to receive an external clock signal and buffer this signal for applying as desired to logic blocks or I/O blocks. Additional types of functional blocks not shown in FIG. 1 are typically provided, for example, blocks of pull-up resistors and three-state buffers which allow an interconnect line to operate as a wired AND or wired OR element.
The internal components of a logic block can perform multiple simple-level functions, some of which are selected when the block is configured. In the Xilinx XC3000 Logic Cell Array Family, for example, a logic block (CLB) such as shown in FIG. 3b includes a combinatorial logic function component 354 which can provide any logic function of up to five input variables, or two functions of up to four input variables each. When a component such as CLB21 of FIG. 1 is programmed, a 32-bit look-up table (not shown) is loaded into the block to be addressed by the input variables a-e (FIG. 3b) during operation. This look-up table is very fast, therefore the signal delay caused by the combinatorial function component 354 is minimal in spite of the flexibility and complexity of the logic block. Because signals internal to a CLB are processed much more rapidly than those which must pass between different CLB's or IOB's of the logic array, it is desirable to group related logic (logic elements connected to a common point) into the same logic block (CLB).
Configurable blocks each have input and output leads for receiving input signals and providing output signals. These leads are shown in FIG. 1 as short lines extending outward from each of the blocks and not connected to other portions of the array. These configurable blocks also have configuration leads for programming the complete logic function of the logic array. The configuration leads of each block determine on which of the other (non-configuration) leads input and output signals will appear, and what logic function will be applied by the block to signals entered on its input leads to generate a signal placed by the block on its output lead or leads.
FIG. 2a shows in more detail a smaller portion of a logic cell array chip with the interconnect lines for connecting one configurable logic block (CLB) or input/output block (IOB) to another CLB or IOB. Some of the interconnect lines are short segments which extend only a short part of the distance across the entire array, and others typically extend in one dimension for the entire length or width of the array. FIG. 2b is a legend showing meanings for the marks in FIG. 2a. FIGS. 2c and 2d show the arrangement of pass transistors for two marks in FIG. 2a. For example, diagonal lines indicate programmable pass transistors for connecting horizontal lines to vertical lines. Each transistor at a diagonal line will have one current carrying terminal connected to a horizontal line and one to a vertical line. The control terminal of the transistor is not shown in FIG. 2a but is connected to a memory cell into which a zero or one is entered when the array is being configured. The zero or one in the memory cell causes the horizontal line to be connected or not connected to the vertical line. As shown in FIGS. 2c and 2d, transistors are also placed at ends of adjacent segmented lines to control the continuity between segments. Each of these transistors is also controlled by a memory cell. A set of memory cells thus controls the configuration of the interconnect lines interconnecting the logic blocks in the array. FIGS. 2a-2d are discussed more fully in U.S. Pat. No. 4,870,302 incorporated herein by reference.
FIG. 3a shows one configurable input/output block (IOB) in an array of IOBs such as IOBs 1-15 shown in FIG. 1 and IOBs 40-11 through 40-15 shown in FIG. 2. Some of the configuration control means are shown in FIG. 3a, for example program-controlled memory cells 311-315 which may invert, multiplex or select a signal. Tri-statable output buffer 321 has its slew rate controlled by slew rate memory cell 314. Some control means in FIG. 3a are not shown, for example the means of controlling TTL/CMOS threshold buffer 324 to respond to a TTL or CMOS voltage level applied to pad 325. The IOB of FIG. 3a can be controlled to receive input signals on I/O pad 325 by turning off output buffer 321, and appropriately setting TTL/CMOS threshold buffer 324. The signal from I/O pad 325 buffered by buffer 324 is available directly on line 344 or as a registered input signal through D-flipflop 323 on line 345. If a registered input signal is desired, the control clock signal on line 348 may be taken from the CK1 line (an internal on-chip clock) by turning on interconnect transistor 327, or from the CK2 line (an external off-chip clock) by turning on interconnect transistor 329. Thus it can be seen that the IOB of FIG. 3a can be configured to perform many different functions.
Similarly, FIG. 3b shows the architecture of one possible configurable logic block (CLB) which can be configured to perform many different logic functions. FIG. 3b shows combinatorial function generator 354 having input lines 381-385 for receiving logic block inputs a-e and input lines 367 and 380 for receiving output signals from D-flipflops 352 and 357 respectively. Combinatorial function generator 354 also provides two combinatorial output functions F and G on lines 374 and 378, each of which may serve as input to either or both flipflops 352 and 357. Output functions F and G may also be provided as logic block output signals X and Y respectively on lines 395 and 396. Which functions are actually implemented by the logic block of FIG. 3b depends upon the settings of configuration control lines not shown in FIG. 3b. Combinatorial function generator 354 can generate any combinatorial function of five variables, or can generate two functions of four variables each. The operation of the logic block of FIG. 3b is described more thoroughly in the Xilinx "Programmable Gate Array Data Book" available from Xilinx, Inc, 2100 Logic Drive, San Jose, Calif. 95124.
A logic array including configurable blocks such as shown in FIGS. 3a and 3b and interconnect lines such as shown in FIG. 2a can be configured to perform a multiplicity of complex logic functions. A logic array is frequently programmed to perform a user-generated complex function represented by a schematic of circuit elements and combinatorial logic gates or by a linked group of Boolean equations.
To assist the designer in converting from an initial schematic design or group of Boolean equations, a set of partitioning, placement, and routing computer programs receives the initial designer information and generates a binary bit stream which is loaded into the logic array and controls all the pass transistors in the entire logic array. Xilinx provides programs specifically tailored for corresponding Xilinx logic array chips.
Major Steps in Configuring a Logic Array Chip
The Xilinx process comprises three major steps: partitioning, placement, and routing. At the partitioning step, the process divides the designer's complex logic function into smaller units, each of which can be implemented by a single CLB or IOB of the intended Xilinx logic array chip. At the placement step, the Xilinx process physically locates (places) each smaller unit in a particular one of the CLBs or IOBs. The routing step determines which interconnect lines to connect between the logic blocks to implement the designer's overall complex logic function.
The partitioning step includes determining how the logic block (CLB or IOB) into which a portion of the schematic is placed will be configured to perform the logic function indicated by that portion of the schematic. Thus the Xilinx method performs sequential steps of partitioning the overall logic function into smaller units (each of the smaller units of logic being performed in a CLB or IOB), placement of these smaller units into specific logic blocks, and routing the interconnect lines between logic blocks.
From files describing the partitioned, placed and routed design, a further step generates the bit stream which, in the subsequent actual programming step, is entered into memory cells for controlling the programmable transistors of the logic cell array chip.
Prior Art Partitioning
FIG. 4 shows steps used by the prior art Xilinx method for partitioning, placing, and routing a designer's initial design into a Xilinx logic cell array. As shown in FIG. 4, the designer started with his original design which may be entered in several ways (i.e. graphic or textual) and may have included several parts.
As shown on the upper left side of FIG. 4, the designer could enter a design using a schematic capture package 412. This capture package 412 could access symbol library 411, which included a symbol library 411 having common logic symbols (AND, NOR, FLIPFLOP, INV, etc.) and additionally logic block symbols for which the designer could specify the contents. Using schematic capture package 412, the designer produced a schematic drawing 413 which incorporated symbols from library 411, connected as specified by the designer. Several schematic capture packages are commercially available, including for example, "Dash-LCA" available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124, "Schema II" available from Xilinx or from Omation, Inc., 801 Presidential Rd., Richardson, Tex. 75081, and "Orcad" available from Orcad Systems, 1049 S.W. Baseline St., Suite 500, Hillsboro, Oreg. 97123.
During this process the designer was able to assign to the combinatorial logic gates and to the lines connecting the gates, "attributes" to be used later such as block name, block location (essential for indicating placement of I/O blocks to be used with existing printed circuit boards), and lines to be kept explicitly exterior to a logic block. By assigning the same "block name attribute" to two different flipflops, the designer could specify that the two flipflops would be assigned to the same logic block. In the prior art partitioning, however, the designer was not able to assign block names to logic gates. The designer could assign an "explicitly external attribute" to a connecting line to prevent this line from being placed inside a logic block. Also, the designer could assign a "clock attribute" to the clock lead of a flipflop to specify that clock lead would be routed to one of two internal clock leads, external clock leads, or to the output of an internal gate in a logic block.
The designer could also specify partitioning by using the special logic block symbols in library 411, discussed above, and specifying the contents of the logic block for which the logic block symbol is used.
Schematic input. As an example, suppose a designer intended to implement a schematic diagram shown in FIG. 5a. Each of the signal lines, combinatorial logic gates, and input/output pads has been given a name by the designer.
After the designer entered the diagram using a schematic capture package 412, the package produced, from the diagram, a schematic drawing 413. Then Xilinx computer program 414 took the designer data of the drawing 413 and created a standard file 415. We call this file an XNF file, which stands for Xilinx external netlist file. A computer program 414 used a library of translations for each of the symbols in schematic drawing 413. Schematic-2XNF programs as represented in block 414 were and are available from Xilinx, Inc. for each of the schematic editors DASH-LCA, Schema II, and Orcad mentioned above. XNF file 415 listed the logic operations performed by each combinatorial logic gate and flipflop and the signal lines that combinatorial logic gate was connected to in drawing 413. XNF file entries for gates and1.sub.-- out, or1.sub.--out, or2.sub.-- out, xor1.sub.-- out and two flipflops would read as follows:
TABLE 1 ______________________________________ XNF File Entries ______________________________________ SYM, and1.sub.-- out, AND PIN, O, O, and1.sub.-- out, PIN, 2, I, and1.sub.-- 2, PIN, 1, I, and1.sub.-- 1, END SYM, or1.sub.-- out, OR PIN, O, O or1.sub.-- out, PIN, 2, I, or1.sub.-- 2, PIN, 1, I, and1.sub.-- out, END SYM, xor1.sub.-- out, XOR PIN, O, O, xor1.sub.-- out, PIN, 2, I, xor1.sub.-- 2, PIN, 1, I, xor1.sub.-- 1, END SYM, q1out, DFF PIN, Q, O, q1out, PIN, D, I, or1.sub.-- out, PIN, C, I, clk.sub.-- out, END SYM, q2out, DFF PIN, Q, O, q2out, PIN, D, I, xor1.sub.-- out, PIN, C, I, clkout, END SYM, or2.sub.-- out, OR PIN, O, O or2.sub.-- out, PIN, 2, I, q2out, PIN, 1, I, q1out, END ______________________________________
The first line begins with the word SYM to indicate a logic symbol will be presented. Next follows a name of the combinatorial logic gate. Next follows the logic function, which must be among the functions recognized by the program. In the first line of Table 1, an AND gate is indicated. On the second line, the word PIN indicates that information about input pins, output pins, or control pins will be presented. An AND gate has only input and output pins and they are designated "I" and "O" respectively. The second line above indicates that pin O of the named AND gate will be an output pin and it will be connected to line "and1.sub.-- out". The third line indicates another pin will be specified, pin 2, which is an input pin, and it will be connected to line "and1.sub.-- 2". The fourth line indicates that pin 1 is also an input pin and it will be connected to line "and1.sub.-- 1". This information completely specifies the connections of a two-input AND gate, therefore the next line "END" indicates the information for that gate is complete. The next entry indicates the combinatorial logic gate used is an OR gate, with connections specified similarly. Connections for the third gate, an exclusive-or gate, are also similarly specified. The fourth entry is indicated to be a D-flipflop (DFF), and subsequent lines specify connections to, respectively, the output pin Q, the data-in pin D, and the clock pin C of the flipflop. No connection to the reset pin of the flipflop is shown. This means that the reset pin is not used. (Therefore no data on the reset pin is provided. The bit stream which controls all pass transistors in the array will disable this reset pin.) Again, "END" indicates information for the flipflop is complete. There would be such entries in the XNF file for every logic gate in the design.
Boolean Input. Alternatively, as shown on the right side of FIG. 4, the designer could type with text editor 416 the Boolean equations of a portion of his design. These Boolean equations would be processed with PALASM program 417 and PDS2XNF program 418 to form XNF file 419. If both schematic and Boolean input are used, XNF file 419 would be merged with XNF file 415 to create a single XNF file 421. XNF file 421 listed conventional logic gates.
There may have been several XNF files if the designer supplied data in more than one format or if the designer designed his system in parts. As indicated in FIG. 4 by XNF merge step 420, the Xilinx program 420 took the separate XNF files and merged them to form a single XNF file 421 comprising the entire information for programming the logic array chip.
The Partitioning Step. As shown in FIG. 4, after merging separate files, the program took XNF file 421 and converted it to a partitioned LCA design file 426 in XNF2LCA step 422. While the XNF file had entries corresponding to each logic gate in the designer's schematic (as shown in Table 1, above), the LCA file 426 had entries corresponding to each logic block in the array.
An algorithm used by one partitioning program performed several steps to partition the designer's schematic into blocks of the logic array chip. The first step was to create groups of combinatorial logic that would source a non-combinatorial gate (i.e., flipflop or output buffer). Working backwards through the network from the source signal of the chosen non-combinatorial gate, the algorithm would gather gates into the group as it followed the gate input signal paths until it encountered a stop condition. In one embodiment, the stop condition included encountering another non-combinatorial gate, encountering a gate which is already assigned to a group, or encountering a point specified by the designer to be outside any logic block. These groups would eventually become the combinatorial logic functions in the configurable logic blocks. This grouping step might result in a group larger than would fit into a logic block.
If so, the partitioning program would reduce the size of the large group to fit into one logic block. Starting with the combinatorial gate which provided the input signal to the non-combinatorial logic gate (flipflop, IO buffer, 3-state buffer, for example), the program would inspect every smaller combination of gates which would fit into the logic block and which sourced the non-combinatorial gate. The program would select the combination which best met the criteria for an optimal group. This set of criteria included preferring
a group with a maximum number of internal signals specified by the designer as `critical`, PA1 a group which reduced the total number of groups resulting from the leftover gates, and PA1 a group which would use more internal feedback signals, a greater number of gates, fewer input signals, and fewer signals specified by the designer as `non-critical`.
When the first optimal group was determined, the program would make a new logic group for each signal which sourced the new optimal group. This group-reduction process would be applied to the new groups if necessary. The optimum group for sourcing the data input pin of a flipflop was then bound to that flipflop so that the flipflop and source group would be treated as a unit.
The next step was to determine which combinatorial logic groups and flipflop/source group units should be placed in the same configurable logic block. Each possible pairing was examined for how many input signals could be shared. By working from the highest to the lowest signal-sharing number, the algorithm would place pairs of flipflop/source group units and combinatorial logic groups into single configurable logic blocks. If two possible pairings would result in the same number of shared signals, the program would choose the pairing that had the highest degree of affinity between the groups or flipflops. Affinity measures how many signals would be shared if the groups were extended at their input ends to include an additional level of logic gates.
FIG. 5a shows a relatively small schematic diagram for which the prior art partitioning, placement and routing will be described. In the example of FIG. 5a, the prior art program of FIG. 4 partitioned the schematic into blocks shown in FIG. 5b. The blocks used are named AA, AB, and P2 through P9. Tables 2 and 3 show the contents of two parts of an LCA file generated by this prior art program to define the partitioned blocks of FIG. 5a.
TABLE 2 ______________________________________ LCA FILE (part 1) ______________________________________ 1 Addnet xor1.sub.-- 2 AB.A P5.I 2 Addnet xor1.sub.-- 1 AB.D P6.I 3 Addnet q2out AA.A AB.X 4 Addnet q1out AA.B AB.Y P3.0 5 Addnet or2.sub.-- out AA.X P2.O 6 Addnet or1.sub.-- 2 AB.B P7.I 7 Addnet clkout AB.K GCLK.0 8 Addnet clkin P4.I GCLK.I 9 Addnet and1.sub.-- 2 AB.C P8.I 10 Addnet and1.sub.-- 1 AB.E P9.I 11 Nameblk AA or2.sub.-- out 12 Editblk AA 13 BASE FG 14 CONFIG X:F Y: RSTDIR: ENCLK: DX: DY: CLK: F:A:B 15 EQUATE F=(A+B) 16 Endblk 17 Nameblk AB q2out 18 Editblk AB 19 BASE FG 20 CONFIG X:QX Y:QY RSTDIR: ENCLK: DX:F DY:G CLK:K F:A:D G:B:C:E 21 EQUATE G=(B+(C*E)) 22 EQUATE F=(A@D) 23 Endblk ______________________________________
The first ten lines of Table 2, which begin with the word "Addnet" identify interconnect network lines to be connected (added) between blocks. The first line indicates that a signal line, named "xor1.sub.-- 2", is to be connected between block "AB", port "A" and block "P5", port "I". Subsequent Addnet lines similarly specify interconnect lines between blocks. Next, the internal configuration of each block is specified. Line 11 names block "AA" as "or2.sub.-- out". Line 12 indicates that the block configuration will be specified (edited) in the lines following. Line 13 indicates that the block is configured as an "FG" block having two outputs which are separate functions of up to 4 variables each, as shown in FIG. 3b. Line 14 indicates the configuration of the "FG" block. The "F" following the "X:" indicates that on the "X" output port (see FIG. 3b) is placed function "F". The space following the "Y:" indicated no function is placed on the "Y" output port. The spaces following the next five colons indicated than these ports will also not be used. DX stands for the data port of the X flipflop 352, DY for the data port of the Y flipflop 357. Labels in FIG. 3b have the following correspondence to labels in Table 2: RSTDIR=RESET, ENCLK=ENABLE CLOCK, CLK=CLOCK. The entry "F:A:B" indicates that the F combinatorial logic function (function 354 of FIG. 3b) will use inputs A and B. Line 15 specifies the particular function F=A+B, meaning that F is to provide the function F=A OR B. In line 16, "Endblk" indicates the configuration of block AA is complete. As shown in FIG. 5b, the function performed by block AB is more complex than that of block AA. Therefore in line 20 of Table 2 the configuration statement for block AB is more complex. Outputs are specified for both the X and Y output ports. The entry "DX:F" indicates the data port of the X flipflop 352 is to receive the F function. Likewise, "DY:G" indicates the data port of the Y flipflop 357 is to receive the G function. The entry "CLK:K" indicates the K port of the block (FIG. 3b, line 388) is to be connected to the CLK ports of the flipflops (as controlled by MUX 360 in FIG. 3b). The next two entries on line 20 of Table 2 indicate that F is to be a function of A and D, and that G is to be a function of B, C, and E. Line 21 specifies that G is B OR (C AND E). Line 22 specifies that F is A XOR D.
Line 25 in Table 3, below, begins configuration of the input/output blocks. Five lines describe each input/output block. The block is first named. The next line indicates that its contents will be specified by the lines following in the table. The next line indicates the kind of block to use is an I/O block, as shown in FIG. 3a. The next line indicates the configuration of the block. In line 28 of Table 3 the entry "IN:I" indicates that block P9 is to be configured to provide the signal from I/O pad 325 on the input port (line 344 in FIG. 3a). The entry "OUT:" indicates that no signal on output port 336 will be provided, and the entry "TRI:" indicates that output buffer 321 will always be enabled. The blocks P3 through P9 are similarly configured in the following lines of Table 3, the last two blocks being configured to provide output from the logic cell array.
TABLE 3 ______________________________________ LCA FILE (part 2) ______________________________________ 25 Nameblk P9 in1 26 Editblk Pq 27 BASE IO 28 CONFIG IN:I OUT: TRI: 29 Endblk 30 Nameblk P8 in2 31 Editblk P8 32 BASE IO 33 CONFIG IN:I OUT: TRI: 34 Endblk 35 Nameblk P7 in3 36 Editblk P7 37 BASE IO 38 CONFIG IN:I OUT: TRI: 39 Endblk 40 Nameblk P6 in4 41 Editblk P6 42 BASE IO 43 CONFIG IN:I OUT: TRI: 44 Endblk 45 Nameblk P5 in5 46 Editblk P5 47 BASE IO 48 CONFIG IN:I OUT: TRI: 49 Endblk 50 Nameblk P4 in6 51 Editblk P4 52 BASE IO 53 CONFIG IN:I OUT: TRI: 54 Endblk 55 Nameblk P3 out1 56 Editblk P3 57 BASE IO 58 CONFIG IN: OUT:O TRI: 59 Endblk 60 Nameblk P2 out2 61 Editblk P2 62 BASE IO 63 CONFIG IN: OUT:O TRI: 64 Endblk ______________________________________
A designer might have preferred that the partitioning into blocks be performed differently, for example, that OR gate "or2.sub.-- out" and flipflop "Q2OUT" be located in the same block, and that flipflop "Q1OUT" be located in a separate block.
One way to accomplish this with the prior art program was to use logic block symbols provided by special Xilinx library of symbols 411 for the schematic capture program 412. For each logic block described by such a logic block symbol, the designer had to type into the computer the block configuration equivalent to lines 11-23 of Table 2. Designers objected to this method because the typing was error-prone and tedious and because the use of the logic block symbols made simulation of their design by logic simulators impossible with existing software.
The prior art method and structure did allow some less tedious ways for designers to put constraints on partitioning. The prior art method and structure allowed the designer to force specific flipflops to be part of the same logic block by giving the same block name attribute or the same "location" parameter to the flipflops, or to force specific flipflops to be part of different logic blocks by giving different block name attributes to them. Also, the designer was able to enter placement constraints 423, FIG. 4, to automatic placement and routing (APR) program 424 to revise the arbitrary placement.
Prior Art Placement and Routing
APR program 424 then completed the placement and routing of all blocks not placed and routed by the designer. Several placement and routing algorithms are available Jiri Soukup, "Circuit Layout", IEEE, vol. 69, Oct. 1981, pp. 1281-1304 gives an overview of the placement and routing problem and discusses several algorithms for placement and routing. Kirkpatrick et al, "Optimization by Simulated Annealing", Science, vol. 220, May 13, 1983, pp. 671-680 discusses a particular algorithm for placement and routing based on the concept of randomly moving elements in a manner analogous to molecular motion in a molten metal, where the algorithm seeks minimum cost of a particular placement and routing as analogous to molecules seeking a position of minimum energy. As with a molten metal, high temperature causes molecules to move temporarily to high energy positions, so with a placement and routing problem, the algorithm causes logic to be moved to high cost locations. As a metal cools, molecules move only to lower energy positions, eventually crystallizing into their final positions, so with the placement and routing problem, the circuit elements move to low cost positions. The algorithm has been found to produce good placement and routing solutions. Such a placement and routing algorithm specifically intended for the logic array chips described above is available by ordering XC-DS23 Automated Design Implementation (A.D.I.) software for IBM PC from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124. The Xilinx placement and routing software is described in Chapter 3 of a manual entitled XACT LCA Development System, Volume II, also available from Xilinx, Inc., which is incorporated herein by reference.
After placement and routing, as shown in FIG. 4, the designer could examine LCA file 426, notice problems, and at step 425, edit placement file 426 (discarding some automatically generated routing). This step could result in the designer replacing routing performed by the computer to meet some requirements not met by the original automatic placement and routing program.
Whatever algorithm is used, there will be applications of the particular program in which the algorithm gives poor results. For example, the prior art partitioning part of the program could sometimes place minimally-related logic together in one logic block that should have been separated so that future placement and routing could succeed. The prior art algorithm would determine the degree of signal sharing and affinity between flipflop and logic groups in the design so that it could assign groups and flipflops with the highest degree of signal sharing and affinity into one logic block. As it worked its way down to the lowest degree of signal sharing and affinity it would sometimes assign two flipflops into the same logic block based only on the fact that they had shared a clock signal. Since it is common to have a single clock signal source many flipflops in a design, this might or might not be an acceptable pairing. If the flipflops are grouped with very different parts of the design, future placement and routing becomes difficult or impossible.
Makebits. The information in LCA file 426 on the configuration of each logic block, its location, and the lines interconnecting it are converted by makebits subroutine 428 to a bit file 429 in which each bit represents the state of a transistor in the logic array, the transistors controlling the connection of interconnect lines between logic blocks in the array and the configuration of the logic blocks themselves.
Configuration. This bit stream from bit file 429 is entered into an array of memory cells in the logic array chip through some of the external pins on the chip. Each memory cell controls one of the transistors in the array of logic blocks. When the memory cells have been set to their proper state, some of the corresponding transistors cause the interconnect lines to be connected as the routing portion of the computer program has specified, and other transistors cause the logic blocks to perform logic functions so that the logic array chip performs the function indicated by the designer's original schematic diagram or other original information.
Unsolved Problems
Designers frequently design their complex logic functions interactively with the programming of the actual logic cell array chip, testing their designs by using and testing the chip. When errors are found or changes are needed, the designer may know what specific changes should be made to the partitioning, placement and routing steps which have been performed automatically. Yet with the prior art when changes to the schematic diagram or Boolean equations were made and the automatic programming was again performed from the beginning, the partitioning, placement and routing may have been different from what the designer expected, causing the logic device to exhibit different electrical characteristics such as signal delay, or even producing an indication from the automatic programming means that the new design would not fit within the array chip. For the example where the automatic means indicated the design would not fit, the designer may have known the design should fit if partitioning were performed in a particular way. Or the designer may have known the design change should not increase response time if partitioning and routing were performed in a particular way.
The prior art program has allowed for manual revision after the partitioning, placement, and routing which the computer has just performed. This manual step interfaced with the designer by displaying the completed layout on a computer monitor and allowing the designer to connect and disconnect interconnect lines between logic blocks and to delete and add connections inside logic blocks. This step gave the designer complete control of the design layout but was extremely cumbersome for the designer. The designer had to have intimate knowledge of the logic array chip to perform this manual step successfully. Further, it was very difficult for the designer to document the editing he performed, and difficult to reproduce the editing when subsequent changes were made.
Another shortcoming of the above prior art method was that it did not allow the designer using schematic entry (Step 412) a way to assign combinatorial logic gates to the same logic block the way flipflops could be assigned to the same logic block. Few designers had the degree of familiarity with the logic array architecture and the format of the configuration information that would have to be typed into the schematic when using symbols from library 411 to directly specify the functionality of a logic block. Thus manual control of the way a schematic diagram would be mapped into a logic cell was not conveniently available.
Furthermore, suppose a designer wished to simulate the design on a logic simulator. While logic simulators recognize standard symbols such as AND, OR, FF, etc. they do not recognize logic block symbols from library 411. Since with the prior art method the computer had no schematic diagram of a logic block entered directly in LCA file format, it was not possible to simulate the logic array if a logic block symbol was used.
Further, the designer may have wished to retain partitioning, placement and routing for identical and tested portions of a design, modifying and testing only small portions of the previous design. With existing automatic methods there was no convenient way to allow for small revisions in the schematic without reimplementing the whole design.